/*
    Alunos:
        Jorge Luis Stefanelli Bonafé	5889794
        Marcelo Koti Kamada             7277670
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <values.h>

#include "mpi.h"

const int INF = MAXINT/2;                                   // constante usada pelo algoritimo de floyd-warshall como peso quando uma juncao nao tem ligacao com outra

int main(int argc, char *argv[]) {
    int n;                                                  // numero de juncoes 2 <= n <= 1000
    int m;                                                  // numero de ruas    n-1 <= m <= (n(n-1))/2

    int A;                                                  // juncao A e' conectada a
    int B;                                                  // juncao B
    int W;                                                  // com comprimento de rua W

    int rc;                                                 // retorno da inicializacao do MPI
    int numtasks, rank;                                     // numero de processos, e id do processo

    rc = MPI_Init(&argc, &argv);                            // inicializa o MPI

    if(rc == MPI_SUCCESS) { 
        MPI_Comm_size(MPI_COMM_WORLD, &numtasks);           // pega o numero de processos
        MPI_Comm_rank(MPI_COMM_WORLD, &rank);               // pego o id do processo

	    if(rank == 0) {
            scanf("%d%d", &n, &m);                          // entra com o numero de juncoes e o numero de ruas
            assert(2 <= n && n <= 1000);                    // o numero de juncoes deve estar entre 2 e 1000
            assert(n-1 <= m && m <= (n*(n-1))/2);           // o numero de ruas deve estar entre n-1 e (n(n-1))/2
        }

        MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);       // broadcast do n e do m, porque so' o processo de rank zero
        MPI_Bcast(&m, 1, MPI_INT, 0, MPI_COMM_WORLD);       // recebeu eles do scanf

        if(rank >= n)                                       // eu nao sei dividir o trabalho quando tem mais processos
            goto end;                                       // do que linhas na matriz, entao o execesso nao faz nada
        if(numtasks > n)                                    // reduz o numero total de processos para o numero de processos que vao fazer alguma coisa
            numtasks = n;

        int *matriz = (int*) malloc(sizeof(int)*n*n);       // aloca matriz de distancias
        assert(matriz != NULL);                             // se a alocacao foi bem sucedida
                                                            // cada linha da matriz e' uma juncao, e as colunas sao as distancais para a outra juncao

        int *matriz_aux = (int*) malloc(sizeof(int)*n);     // matriz_aux[i] serve para armazenar qual processo vai ser responsavel pela linha que tem indice i
        assert(matriz_aux != NULL);

        int i, j;
        for(i = 0; i < n; i++)                              // inicializa a matriz com distancias infinitas ate as outras juncoes, 
            for(j = 0; j < n; j++) {                        // pq ainda nao sabemos quais as distancias
                matriz[i*n+j] = INF;
            }

        if(rank == 0) {                                     // leitura das distancias W entre as juncoes A e B, pelo processo zero
            for(i = 0; i < m; i++) {                        // os outros processos vao receber os dados via broadcast
                scanf("%d%d%d", &A, &B, &W);                // leitura de A, B e W
                A--;                                        // decrementa A e B
                B--;                                        // porque a matriz comeca do zero, e na entrada as juncoes comecam do um
                assert(A < n && B < n);                     // verifica se os indices estao dentro da matriz
                matriz[A*n+B] = W;                          // atribui tanto a A para B, quanto de B para A
                matriz[B*n+A] = W;                          // porque as ruas sao ambos os sentidos
            }
        }

        // roda o algoritimo de Floyd-Warshall, para calcular as distancias
        int k;                                                      // k do floyd-warshall
        int id;                                                     // id serve para saber qual o id do processo que vai receber a tarefa
        if(rank == 0) {                                             // o processo zero
            int aux;
            for(k = 0; k < n; k++) {
                for(aux = 0; aux < n; aux++)                        // reseta a matriz aux com -1
                    matriz_aux[aux] = -1;
                MPI_Bcast(&matriz[k*n], n, MPI_INT, 0, MPI_COMM_WORLD); // manda a linha comum que todos os processos vao precisar

                id = 1;                                             // como o processo zero so' vai ficar responsavel por coordenar os outros, o processo 1 vai ser o primeiro a receber trabalho
                for(i = 0; i < n; i++) {                            // percorre as linhas da matriz e ve qual processo vai ser responsavel por ela
                    if(i != k && matriz[i*n+k] < INF) {             // if do floyd-warshall, que tira a diagonal
                        matriz_aux[i] = (id%numtasks);              // matriz_aux[i] = valor, tem i = numero da linha da matriz, valor = numero do id do processo que vai processar a linha i
                        id++;                                       // proximo id
                        if(id == numtasks)                          // reseta o id quando ele for o ultimo processo
                            id = 1;
                    }
                }
                MPI_Bcast(matriz_aux, n, MPI_INT, 0, MPI_COMM_WORLD);   // manda a matriz_aux para os outros processos

                for(i = 0; i < n; i++) {                            // esse for manda a linha especifica que cada processo precisa
                    aux = matriz_aux[i];
                    if(aux >= 0)
                        MPI_Send(&matriz[i*n], n, MPI_INT, aux, 0, MPI_COMM_WORLD);
                }
                for(i = 0; i < n; i++) {                            // recebe as linhas dos processos
                    aux = matriz_aux[i];                            // e monta a matriz de volta, so' que agora ela esta atualizada
                    if(aux >= 0)
                        MPI_Recv(&matriz[i*n], n, MPI_INT, aux, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                }
            }
            // quando termina todas as iteracoes do Floyd-Warshall
            int max = INF;
            int tmp;
            for(i = 1; i < numtasks; i++) {                         // recebo de todos os processos, as maiores distancias das linhas que eles calcularam
                MPI_Recv(&tmp, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                if(max > tmp)                                       // e pego o menor deles, pois a menor distancia das maiores distancias
                    max = tmp;                                      // e' a resposta para o problema
            }
            //printf("resultado %d\n", max);
            printf("%d\n", max);
        }
        else {
            int tmp;
            int size;
            int *linhas = (int*) malloc(sizeof(int) * n);           // vetor que tem quais linhas da matriz o processo vai trabalhar, serve que nem uma fila
            for(k = 0; k < n; k++) {                                                    // cada processo vai receber dados n vezes do processo zero
                size = 0;
                MPI_Bcast(&matriz[k*n], n, MPI_INT, 0, MPI_COMM_WORLD);                 // recebe uma linha comum que todos os processos precisam
                MPI_Bcast(matriz_aux, n, MPI_INT, 0, MPI_COMM_WORLD);                   // recebe a matriz aux, que tem qual linha cada processo vai trabalhar   

                for(i = 0; i < n; i++)                                                  // percorre matriz aux para ver quais linhas este processo vai trabalhar
                    if(matriz_aux[i] == rank) {                                         // e ja monta o vetor linhas para nao precisar fazer outro for no matriz_aux
                        MPI_Recv(&matriz[i*n], n, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                        linhas[size] = i;
                        size++;
                    }

                for(tmp = 0; tmp < size; tmp++) {                                   // percorre o vetor linhas
                    i = linhas[tmp];                                                // pegando as linhas que o processo vai trabalhar
                    for(j = 0; j < n; j++) {                                        // processa a linha l com floyd-warshall
                        if(matriz[i*n+j] > matriz[i*n+k] + matriz[k*n+j])           // if do floyd-warshall
                            matriz[i*n+j] = matriz[i*n+k] + matriz[k*n+j];
                    }
                    MPI_Send(&matriz[i*n], n, MPI_INT, 0, 0, MPI_COMM_WORLD);       // manda o resultado para o processo zero
                }
            }
            // depois que terminou o floyd-warshall
            int max = 0;
            tmp = INF;
            int pi;
            for(pi = 0; pi < size; pi++) {                                          // dentre as linhas que o processo ainda tem que estao atualizadas
                i = linhas[pi];                                                     // eu pego uma por uma
                for(j = 0; j < n; j++)                                              // e vejo qual a maior distancia desta linha
                    if(i != j && max < matriz[i*n+j])
                        max = matriz[i*n+j];
                if(tmp > max)                                                       // dentre as maiores distancias, eu pego a menor
                    tmp = max;
            }
            MPI_Send(&tmp, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);                       // mando a menor das maiores distancias para o processo zero
            free(linhas);
        }
        free(matriz);                             // desaloca matriz
        free(matriz_aux);
    }
end:
    MPI_Finalize();
    return 0;
}

